package demo2;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode30 {
    public List<Integer> findSubstring(String s, String[] words) {
        char[] arrs = s.toCharArray();
        int ns = arrs.length, nw = words.length;
        int len = words[0].length();
        Map<String, Integer> hashw = new HashMap<>();
        for (String str : words) hashw.put(str, hashw.getOrDefault(str, 0) + 1);
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            Map<String, Integer> hasha = new HashMap<>();
            for (int left = i, right = i, k = 0; right <= ns - len; right += len) {
                String in = s.substring(right, right + len);
                hasha.put(in, hasha.getOrDefault(in, 0) + 1);
                if (hasha.get(in) <= hashw.getOrDefault(in, 0)) k++;
                if (right - left + 1 > len * nw) {
                    String out = s.substring(left, left + len);
                    if (hasha.get(out) <= hashw.getOrDefault(out, 0)) k--;
                    hasha.put(out, hasha.get(out) - 1);
                    left += len;
                }
                if (k == nw) list.add(left);
            }
        }
        return list;
    }
}
